import java.util.ArrayList;
import java.util.List;

class Solution {
    public static List<List<Integer>>  generate(int numRows) {
        //先构建返回值 返回值是一个二维数组
        List<List<Integer>> ret = new ArrayList<>();
        //1.先打第一行
        List<Integer> num1 = new ArrayList<>();
        num1.add(1);
        num1.add(2);
        ret.add(num1);
        //2.打印第i行
        for(int i = 1; i<numRows;i++){
            //当前第i行
            List<Integer> curRow = new ArrayList<>();
            //每行先打印1
            curRow.add(1);
            //每行中间位置 等于上一行的两个数相加
            List<Integer> preRow = ret.get(i-1);
            //j重第二个数开始:j=1; 第i行有i个数,且循环里面只计算每行中间的数: j<i
             for(int j = 1; j<i;j++){
                 int num = preRow.get(j)+preRow.get(j-1);
                 curRow.add(num);
             }
             //第i行的最后一个数也是1
             curRow.add(1);
             //将这行add到ret里
            ret.add(curRow);
        }
        return ret;
    }

    public static void main(String[] args) {
        generate(5);
    }
}